"""
lc399 除法求值
给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。

另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请你根据已知条件找出 Cj / Dj = ? 的结果作为答案。

返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替代这个答案。

注意：输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。

示例 1：

输入：equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
输出：[6.00000,0.50000,-1.00000,1.00000,-1.00000]
解释：
条件：a / b = 2.0, b / c = 3.0
问题：a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
结果：[6.0, 0.5, -1.0, 1.0, -1.0 ]

"""
"""并查集解法"""

from typing import List


class Solution:
    def calcEquation(
        self, equations: List[List[str]], values: List[float], queries: List[List[str]]
    ) -> List[float]:
        u, N, ans = self.Union(equations), len(equations), []
        #  breakpoint()
        for i in range(N):
            u.union(equations[i][0], equations[i][1], values[i])

        #  breakpoint()
        print(u.weight)
        for x, y in queries:
            ans.append(u.isConnected(x, y))
        return ans

    # class inside class
    class Union:
        def __init__(self, equations):
            self.parent, self.weight = {}, {}
            for nodes in equations:
                for x in nodes:
                    if x not in self.parent:
                        # store all the node, initialize the union set
                        self.parent[x], self.weight[x] = x, 1

        def find(self, x):
            if self.parent[x] != x:
                parent = self.parent[x]
                self.parent[x] = self.find(parent)
                self.weight[x] *= self.weight[parent]
            # compress the path
            return self.parent[x]

        def union(self, x, y, value):
            rootX = self.find(x)
            rootY = self.find(y)
            if rootX != rootY:
                self.parent[rootX] = rootY
                self.weight[rootX] = self.weight[y] * value / self.weight[x]

        def isConnected(self, x, y):
            if x in self.parent and y in self.parent:
                # 重新进行了路径压缩
                rootX, rootY = self.find(x), self.find(y)
                if rootX == rootY:
                    #  breakpoint()

                    return self.weight[x] / self.weight[y]
            return -1


class Solution_wxz:
    def calcEquation(
        self, equations: List[List[str]], values: List[float], queries: List[List[str]]
    ) -> List[float]:
        unionset = self.UnionSet(equations)
        res = []

        for key, value in enumerate(values):
            unionset.union(equations[key][0], equations[key][1], value)

        for query in queries:
            res.append(unionset.is_connected(query[0], query[1]))
        return res

    class UnionSet:
        def __init__(self, equations):
            self.parent = {}
            self.weight = {}
            for equation in equations:
                for node in equation:
                    if node not in self.parent:
                        self.parent[node] = node
                        self.weight[node] = 1

        def find(self, x):
            if self.parent[x] != x:
                parent = self.parent[x]
                self.parent[x] = self.find(parent)
                self.weight[x] *= self.weight[parent]
            return self.parent[x]

        def union(self, x, y, value):
            ...
            root_x = self.find(x)
            root_y = self.find(y)

            if root_x != root_y:
                self.parent[root_x] = root_y
                self.weight[root_x] = self.weight[y] * value / self.weight[x]
            return

        def is_connected(self, x, y):
            ...
            if x in self.parent and y in self.parent:
                root_x = self.find(x)
                root_y = self.find(y)
                if root_x == root_y:
                    return self.weight[x] / self.weight[y]
            return -1


equations = [["b", "c"], ["a", "b"]]
values = [3.0, 2.0]
queries = [["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"]]
a = Solution()
print(a.calcEquation(equations, values, queries))
